package recursion.eightQueen;

/**
 * 参考：https://blog.csdn.net/u013278314/article/details/83819141
 *
 */
public class eightQueenOfDeath {
    // 皇后的个数也就是棋盘的大小
    private static final int QUEEN_NUM = 6;
    // 定义一个棋盘
    private static final int[][] checkBoard = new int[QUEEN_NUM][QUEEN_NUM];
    // 定义共有多少种放置皇后的算法
    private static int COUNT = 0;

    /**
     * 打印棋盘
     */
    public static final void display(){
        System.out.println("第"+(++COUNT)+"次摆法");
        for (int i = 0; i < QUEEN_NUM; i++) {
            for (int j = 0; j < QUEEN_NUM; j++) {
                System.out.print(checkBoard[i][j]+" ");
            }
            System.out.println("");
        }
    }
    /**
     *判断当前位置能否放置皇后
     */
    public static final boolean check(int row,int col){
        // 如果当前位置的上面有皇后
        for (int i = row-1; i >=0; i--) {
            if (checkBoard[i][col]==1)
                return false;
        }
        // 查看左上斜线是否有皇后
        for (int i = row-1, j =col-1 ; i>=0 && j>=0;i--,j--) {
            if (checkBoard[i][j]==1)
                return false;
        }
        // 查看右上斜线是否有皇后
        for (int i = row-1, j =col+1 ; i>=0 && j<QUEEN_NUM;i--,j++) {
            if (checkBoard[i][j]==1)
                return false;
        }
        return true;
    }

    /**
     * 回朔
     * @param row
     */
    public static final void play(int row){
        // 遍历当前行的所有单元格，以列为单位
        for (int i = 0; i < QUEEN_NUM; i++) {
            if (check(row,i)){
                checkBoard[row][i] = 1;
                if(row!=QUEEN_NUM-1){
                    play(row+1);
                }
                if (row==QUEEN_NUM-1){
                    display();
                }
                // 回朔到当前步骤，把皇后设置为0
                // 因为传递的是引用类型，还记得i ,j 的值。 每一个栈中都保存着独立的数组信息
                checkBoard[row][i] = 0;
            }
        }
    }
    public static void main(String[] args) {
        play(0);
    }
}
